Masala #0852

Rabin - Karp algoritmini urganish jarayonida qiziq bir narsa meni o'ylantirib qoldi. Sizga inglizcha harflardan iborat s satr beriladi. s satrni Pastki qator(substring)$s[l...r](1 \leq l \leq r \leq \vert s \vert)$ larida yomon deb berilgan harflar soni ko'pi bilan k ta bo'lganlari sonini toping.
Agar 2 ta $s[x...y] ≠ s[p...q]$ bo'lmasa ular har xil hisoblanadi, yani mano jihatidan bir xil bo'lmasligi kerak.

Birinchi qatorda s satr uzunligi 1500 dan oshmaydi.
Ikkinchi qatorda  26 ta harf uchun yaxshi yoki yomon ekanini belgilovchi '0' va '1' lardan iborat satr kiritiladi('0' bo'lsa yomon , '1' bo'lsa yaxshi).
Ohirgi qatorda k($0 \leq k \leq |s|$) butun son kiritiladi.

Berilgan shartni qanoatlantiruvchi satrlar sonini toping.